package com.xigua._数学;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 * @author LiRongHua
 * @Title: ${file_name}
 * @Package ${package_name}
 * @Description: 给定一个可能含有重复元素的整数数组，要求随机输出给定的数字的索引。 您可以假设给定的数字一定存在于数组中。
 *注意：
 *数组大小可能非常大。 使用太多额外空间的解决方案将不会通过测试。
 * @date 2022/2/1014:33
 */
public class _398_随机数索引 {

    public static void main(String[] args) {
        _398_随机数索引 test = new _398_随机数索引(new int[]{1,2,2,3,3,3});
        System.out.println(test.pick1(3));
    }

    private int[] nums;

    public _398_随机数索引(int[] nums) {
        this.nums = nums;
    }

    public int pick(int target) {
        List<Integer> list = new ArrayList<>();
        Random random = new Random();
        for (int i = 0; i < this.nums.length; i++) {
            if (nums[i] == target) list.add(i);
        }
        return list.get(random.nextInt(list.size()));
    }

    /**
     * 蓄水池抽样问题
     * @param target
     * @return
     */
    public int pick1(int target) {
        int count = 0;
        int index = 0;
        Random random = new Random();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target){
                count++;
                if (random.nextInt() % count ==0) index = i;
            }
        }
        return index;
    }
}
